package exercise.week01;

import java.util.*;

/**
 * 7届-决赛-JavaB-2
 * 反幻方
 * 我国古籍很早就记载着
 * 2 9 4
 * 7 5 3
 * 6 1 8
 * 这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。
 * <p>
 * 下面考虑一个相反的问题。
 * 可不可以用 1~9 的数字填入九宫格。
 * 使得：每行每列每个对角线上的数字和都互不相等呢？
 * 这应该能做到。
 * 比如：
 * 9 1 2
 * 8 4 3
 * 7 5 6
 * 你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。
 * 旋转或镜像算同一种。
 * 比如：
 * 9 1 2
 * 8 4 3
 * 7 5 6
 * <p>
 * 7 8 9
 * 5 4 1
 * 6 3 2
 * <p>
 * 2 1 9
 * 3 4 8
 * 6 5 7
 * 等都算作同一种情况。
 * <p>
 * 请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。
 */
public class T2 {
    private static int count = 0;

    public static void main(String[] args) {
        //Key：1-9 Value：是否被使用过
        HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for (int i = 1; i <= 9; i++) {
            map.put(i, false);
        }
        LinkedList<Integer> list = new LinkedList<Integer>();//存储结果
        dfs(map, 1, list);//深度优先搜索
        System.out.println(count / 8);//旋转或镜像会有8种不同形态但算同一种情况
    }

    public static void dfs(HashMap<Integer, Boolean> map, int level, LinkedList<Integer> result) {
        //1.截止条件
        if (level > map.size()) {
            //截止后说明一个完整的排列已经生成，可以开始计算行、列、对角线的和
            int row1 = result.get(0) + result.get(1) + result.get(2);
            int row2 = result.get(3) + result.get(4) + result.get(5);
            int row3 = result.get(6) + result.get(7) + result.get(8);
            int col1 = result.get(0) + result.get(3) + result.get(6);
            int col2 = result.get(1) + result.get(4) + result.get(7);
            int col3 = result.get(2) + result.get(5) + result.get(8);
            int diag1 = result.get(0) + result.get(4) + result.get(8);
            int diag2 = result.get(2) + result.get(4) + result.get(6);
            /**
             * 创建一个Set集合，将这些结果存入set中，如果最终set集合中的元素数量不是8，说明有重复的元素
             */
            HashSet<Integer> set = new HashSet<Integer>();
            Collections.addAll(set, row1, row2, row3, col1, col2, col3, diag1, diag2);
            if (set.size() == 8) {
                count++;
            }
            return;
        }
        //2.候选结点
        for (int i = 1; i <= map.size(); i++) {
            //筛选
            if (!map.get(i)) {
                result.push(i);//当前结点的值没有被使用过则可以加入结果集
                map.put(i, true);//加入结果集后要改变状态
                dfs(map, level + 1, result);
                result.pop();//通过出栈将结果集初始化
                map.put(i, false);//将各个结点的使用状态初始化
            }
        }
    }
}
